package ru.susu.algebra.partition.polyhedron.providers;

import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;
import java.util.Map.Entry;

import ru.susu.algebra.pair.Pair;
import ru.susu.algebra.partition.Partition;
import ru.susu.algebra.partition.PartitionsFactory;
import ru.susu.algebra.partition.vectex.Partition2VertexCache;

/**
 * @author akargapolov
 * @since: 11.03.2010
 */
public class RecursiveVertexesProvider implements IVertexesProvider
{

	@Override
	public List<Partition> getVertexes(int number, Map<Integer, Set<Partition>> oldVertexes)
	{
		TreeMap<Partition, Integer> tmpResult = new TreeMap<Partition, Integer>();

		for (int oldNumber = 1; oldNumber < number; oldNumber++)
			for (Partition p : oldVertexes.get(oldNumber))
			{
				Partition newP = p.clone();
				newP.add(number - oldNumber);
				Integer prev = !tmpResult.containsKey(newP) ? 0 : tmpResult.get(newP);
				tmpResult.put(newP, prev + 1);	//подсчитываем количество способов получить newP
			}

		List<Partition> result = new ArrayList<Partition>();

		for (Entry<Partition, Integer> entry : tmpResult.entrySet())
		{
			Partition p = entry.getKey();
			Integer value = entry.getValue();
			Pair<Integer, Integer>[] array = Partition2VertexCache.getPairs(p) ;

			//каждый не нулевой элемент должен быть получен из предыдущих вершин прибавлением единицы
			if (array.length == value)
			{
				result.add(p);
			}
		}
		result.add(PartitionsFactory.createPartition(new Integer[]{number}));
		//result.add(new PlainPartition(new Integer[]{number}));
		return result;
	}

}
